//
// Created by Lenovo on 2024/3/3.
//
#include<bits/stdc++.h>
using namespace std;
class Solution {
public:

    int n;
    int count;
    int go[4][2]={{1,0},{-1,0},{0,-1},{0,1}};
    bool visited[510][510];


    void dfs(int x,int y,int mark,vector<vector<int>>& grid){
        for(int i=0;i<4;i++){
            int nextx=x+go[i][0];
            int nexty=y+go[i][1];
            if(nextx>=0 && nextx<n && nexty>=0 && nexty<n && !visited[nextx][nexty] && grid[nextx][nexty]==1){
                visited[nextx][nexty]=true;
                grid[nextx][nexty]=mark;
                count++;
                dfs(nextx,nexty,mark,grid);
            }
        }
    }

    int largestIsland(vector<vector<int>>& grid) {
        n=grid.size();
        map<int,int> gridMap;        //key--岛屿标记,value--岛屿的面积
        int mark=2;                 //岛屿标记，从2开始
        bool isAll1=true;           //是否全1
        //(1).统计各个岛屿的面积，并给每个岛屿标号
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(grid[i][j]==0) isAll1=false;
                if(!visited[i][j] && grid[i][j]==1){
                    count=0;
                    visited[i][j]=true;
                    grid[i][j]=mark;
                    count++;
                    dfs(i,j,mark,grid);
                    gridMap[mark]=count;
                    mark++;
                }
            }
        }
        //全1,直接返回
        if(isAll1) return n*n;
        //(2).遍历所有为0的单元格，访问周围的岛屿，计算把他变成1之后的总面积
        int result=0;
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(grid[i][j]==0){
                    set<int> gridSet;        //记录当前0变成1后已经连通的岛屿(标记号)
                    int num=1;              //当前总数量
                    //遍历周围的点
                    for(int k=0;k<4;k++){
                        int nextx=i+go[k][0];
                        int nexty=j+go[k][1];
                        if(nextx>=0 && nextx<n && nexty>=0 && nexty<n && grid[nextx][nexty]>=2){
                            int no=grid[nextx][nexty];
                            if(gridSet.find(no)!=gridSet.end()) continue;
                            num+=gridMap[no];
                            gridSet.insert(no);
                        }
                    }
                    result=max(result,num);
                }
            }
        }
        return result;
    }
};